package formal.array;

import java.util.HashMap;
import java.util.Map;

/**
 * @author DengYuan2
 * @create 2021-02-07 21:06
 */
public class E_697 {
    public static void main(String[] args) {
        int[] a = {1, 2, 2, 3, 1, 4, 2, 1, 2, 1};
        int res = findShortestSubArray(a);
        System.out.println(res);
    }

    /**
     * 我的思路：用map，key为数组值，value为int[]数组，分别存放开始索引，目前为止的结束索引，值出现的个数
     *
     * @param nums
     * @return
     */
    public static int findShortestSubArray(int[] nums) {
        int max = 1;
        int maxIdx = 0;
        HashMap<Integer, int[]> map = new HashMap<>(16);
        for (int i = 0; i < nums.length; i++) {
            if (map.containsKey(nums[i])) {
                int[] data = map.get(nums[i]);
                data[1] = i;
                data[2]++;
                if (data[2] > max) {
                    max = data[2];
                    maxIdx = i;
                } else if (data[2] == max) {
                    int[] other = map.get(nums[maxIdx]);
                    if (data[1] - data[0] < other[1] - other[0]) {
                        maxIdx = i;
                    }
                }
                map.put(nums[i], data);
            } else {
                map.put(nums[i], new int[]{i, i, 1});
            }
        }

        int[] res = map.get(nums[maxIdx]);
        return res[1] - res[0] + 1;

    }

    /**
     * 大神用了3个map，思路基本差不多，但比我的还慢，哈哈哈哈哈
     *
     * @param nums
     * @return
     */
    public static int findShortestSubArray2(int[] nums) {
        Map<Integer, Integer> numsCnt = new HashMap<>();
        Map<Integer, Integer> numsLastIndex = new HashMap<>();
        Map<Integer, Integer> numsFirstIndex = new HashMap<>();
        for (int i = 0; i < nums.length; i++) {
            int num = nums[i];
            numsCnt.put(num, numsCnt.getOrDefault(num, 0) + 1);
            numsLastIndex.put(num, i);
            if (!numsFirstIndex.containsKey(num)) {
                numsFirstIndex.put(num, i);
            }
        }
        int maxCnt = 0;
        for (int num : nums) {
            maxCnt = Math.max(maxCnt, numsCnt.get(num));
        }
        int ret = nums.length;
        for (int i = 0; i < nums.length; i++) {
            int num = nums[i];
            int cnt = numsCnt.get(num);
            if (cnt != maxCnt) continue;
            ret = Math.min(ret, numsLastIndex.get(num) - numsFirstIndex.get(num) + 1);
        }
        return ret;
    }

    /**
     * 官方-计数排序
     * -也有改进版本的
     *
     * @param nums
     * @return
     */
    public static int findShortestSubArray3(int[] nums) {
        int[] count = new int[50000];
        int max = 0;
        for (int i = 0; i < nums.length; i++) {
            max = Math.max(max, ++count[nums[i]]);
        }
        if (max == 1) {
            return 1;
        }
        int res = nums.length;
        for (int i = 0; i < count.length; i++) {
            if (count[i] != max) {
                break;
            }
            int start = 0, end = nums.length - 1;
            while (start < end && nums[start] != i) {
                start++;
            }
            while (start < end && nums[end] != i) {
                end--;
            }
            res = Math.min(start - end + 1, res);
        }


        return res;
    }

    /**
     * 官方-计数排序-优化
     * @param nums
     * @return
     */
    public int findShortestSubArray4(int[] nums) {
        // 找到数组中的最小数和最大数
        int max = Integer.MIN_VALUE, min = Integer.MAX_VALUE;
        for (int i : nums) {
            max = Math.max(max, i);
            min = Math.min(min, i);
        }
        // 使用计数排序的思想
        int[] count = new int[max - min + 1];
        // 记录出现最高的次数是多少次数
        int degree = 0;
        for (int i : nums) {
            degree = Math.max(degree, ++count[i - min]);
        }
        // 如果数组的度为 1，则结果必为 1
        if (degree == 1) {
            return 1;
        }
        int result = nums.length;
        for (int i = 0; i < count.length; i++) {
            if (degree != count[i]) {
                continue;
            }
            // 还原原数的值
            int tmp = min + i;
            // 求该数出现的起始和结束的下标
            int start = 0, end = nums.length - 1;
            while (start < end && tmp != nums[start]) {
                start++;
            }
            while (start < end && tmp != nums[end]) {
                end--;
            }
            result = Math.min(result, end - start + 1);
        }
        return result;
    }


}
